package src.dp.stock;

public class no123 {//股票3，至多买卖两次

    /**
     * 1. dp数组下标含义：
     * 由于限制买卖两次，所以细分为第一次第二次，又多了几个状态
     * 分别用dp[i][0] ~ dp[i][4]表示
     */
    public int maxProfit(int[] prices) {
        int len = prices.length;
        int[][] dp = new int[len][5];

        dp[0][0] = 0;  //不操作，其实这个状态可有可无，删去他不影响结果
        dp[0][1] = -prices[0];  //第一次持有
        dp[0][2] = 0;  //第一次不持有
        dp[0][3] = -prices[0];  //第二次持有
        dp[0][4] = 0;  //第二次不持有

        for (int i = 1; i < len; i++) {

            dp[i][0] = dp[i - 1][0];  //可删去这一行
            dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
            dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
            dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
            dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
        }
        //return Math.max(dp[len - 1][2], dp[len - 1][4]);
        //其实不用比较，因为第二次卖出的最大值已经包括了第一次，相当于dp[len-1][2]最大后，再原地买卖一次变dp[len-1][4]
        return dp[len - 1][4];

    }
}
